The present invention relates to a scheduling method of a process of a computer system, and in particular to a process scheduling for periodically starting each process and bandwidth assurance in data communication using a CSMA/CD system.
C. Venkatramani, et al, Design, Implementation, and Evaluation of a Software-based Real-Time Ethernet Protocol, SIGCOMM '95 Cambridge, pp. 27–37, and C. Venkatramani, The Design, Implementation, and Evaluation of RETHER: A Real-Time Ethernet Protocol, Dept. of Computer Science, State University of New York at Stony Brook, 1996, pp. 1–125 describe an Ethernet protocol, hardwares and real-time and non-real-time communication.
JP-A-3-155241 teaches a LAN system using synchronous and asynchronous communication transfer slots.
Conventionally as the scheduling method of a process for conducting continuous media, a scheduling method using the “Conductor/Performer” model is known. (Nishio et al., “Conductor/Performer,” 1st International Workshop on Real-Time Operating Systems and Applications, 1994.) The term “continuous media processing” means processing for converting and transferring data obtained by digitizing images or speech.
In the case where only one stream exists in a system, this method assures any process belonging to the stream of being periodically scheduled. Herein, however, the term “stream” means a group of processes delivering worked continuous media data directly or indirectly to each other. Each of processes belonging to the same stream are provided with the unique order of conducting the work processing of continuous media data. The top process obtains input of the continuous media data from an external device (such as a video digitizer). Each of subsequent processes receives continuous media data worked by a process immediately preceding in order from the immediately preceding process, conducts data work (such as compression processing) to be conducted by itself, and delivers continuous media data worked by itself to a process immediately succeeding in order. The last process outputs continuous media data to the external device (such as a network adapter).
A summary of a scheduling method using a Conductor/Performer model will be hereafter described. For each stream, one periodically driven Conductor process is prepared. The order of Performer processes (i.e., processes belonging to the stream) to be started by the Conductor process is registered beforehand. In accordance with this registered order, the Conductor process starts a Performer process. Therefore, each of both the Conductor process and the Performer processes holds a message queue for wakeup notice of its own process. Wakeup of another process is conducted by transmitting a message to a message queue held by the process.
The Conductor process is driven at time intervals each equal to a specified period. In accordance with the registered order of the Performer processes, the Conductor process repetitively issues a call (function call) for transmitting a message to a message queue owned by the next Performer process in the order and waiting the arrival of a message at a message queue owned by the Conductor process. In other words, the Conductor process repeats the wakeup of a Performer process and sleep lasting until the started Performer process completes the execution of one period. If the last Performer process in order has completed execution, the Conductor process sleeps until the next periodically driven trigger is applied by a timer interrupt.
On the other hand, a Performer process wakes up upon receiving a message from the Conductor process, and conducts continuous media processing corresponding to one period. Upon completing the continuous media processing corresponding to one period, the Performer process issues a call for transmitting a message to a message queue owned by the Conductor process and waiting for the arrival of a message at a message queue owned by its own process. The Performer process sleeps until a message for notifying the wakeup of the next period is transmitted from the Conductor process.
In the case where only one stream exists in the system, the above described scheduling method assures a CPU of being periodically allocated to a Performer process.
The communication methods that have been used ordinarily in the LAN include a CSMA/CD system. Data transfer in data communication using this CSMA/CD system is executed in the following procedures.
a. A node or a computer requesting data transfer confirms the status of a stream.
b. Data transfer is commenced when the stress is empty, and is held on till the stream is empty, when the stream is not empty.
c. The node transferring the data compares the transmitted data with the status of the stream, and a plurality of nodes execute simultaneously the data transfer on the same stream and monitor whether or not any data collision occurs.
d. When the node transferring the data detects the data collision before the transfer is completed, it stops the transfer and transmits a collision signal representing the occurrence of the data collision to all the nodes on the stream.
e. The node transferring the data similarly stops the data transfer when it receives the collision signal before the data transfer is completed.
f. When the node transferring the data stops the data transfer in the case of the procedure d or e, a wait time is secured at random and then the data transfer procedure is repeated once again from the beginning.
g. When the data transfer is completed successfully by the procedures a to f, normal transfer completion is returned to the transfer request.
h. When the data transfer proves failure more than a predetermined number of times due to the data collision by the procedures a to d, the data transfer is stopped and a transfer error is sent back to the transfer request.
The node to which the data transfer is generated from the application, or the like, commences the data transfer at any time by the procedures described above.
According to this communication method, the stream is not occupied even during the transfer of large quantities of data and the node to which the data transfer request is generated can start the data transfer by interrupting the transfer of large quantities of data. Therefore, this method has been used widely in the conventional data transfer which does not need the real-time feature.
In the data transfer of the CSMA/CD system, however, the loss of a packet or a lump of data as the data transfer unit, and delay, occur due to the collision with other data transfer. The problem of the loss of the packet, etc. can be solved by detecting time-out and executing re-transfer of the data in the data transfer that does not need the real-time feature. Nonetheless, the existing LAN using the CSMA/CD system cannot easily achieve communication that guarantees the real-time feature because the delay of the packet and the data re-transfer spoil the real-time feature of the communication.
A multimedia LAN system as one of the examples of the prior art technologies for solving such a problem is described in JP-A-3-155241.
The multimedia LAN system includes a specific apparatus for establishing synchronism as a whole among all the computers constituting the LAN system. To establish this synchronism throughout the whole LAN system, a time-slot for synchronization signal transfer, a time-slot for synchronous data transfer and a time-slot for asynchronous data transfer are disposed so that real-time multimedia data are transferred in a predetermined time interval in the time-slot for synchronization transfer while the time-slot for asynchronous signal transfer makes it possible to execute data transfer not requiring real-time feature by using an access system such as a CSMA/CD system.
In the scheduling method according to the Conductor/Performer model, the following problems occur in the case where a plurality of streams exist in a system.
(a) The priority of each of the Conductor processes and Performer processes does not change with time. In the case where Conductor processes having different drive periods are mixedly present, the execution start interval of the Conductor processes varies. In other words, when a Conductor process has been waked up, there is a possibility that another Conductor process or another Performer process having the same priority or higher priority is executing. In other words, access contention of the CPU time occurs between the Conductor process waked up and another Conductor process or another Performer process. As a result, the execution start interval of the Conductor process varies, and the execution interval of subsequent Performer process also varies.
(b) Since wakeup notice is conducted by inter-process communication (IPC), function calls of message transmission and message reception occur and overhead caused by wakeup notice is large.
These problems make it difficult to realize continuous media processing required to yield high throughput, such as real time MPEG compression processing of multimedia data. Unless in such processing the buffer management at the time of continuous media data input is conducted without use of an interrupt, sufficient throughput is not obtained because of the interrupt overhead. Even in the case where a plurality of streams exist in the system, therefore, it is necessary to keep the execution interval of a Performer process constant as far as possible and it is necessary for a Performer process to spontaneously change over the input buffer without a notice using an interrupt. In the same way, the overhead of the IPC used for wakeup notice also decreases the throughput.
Furthermore, in the scheduling method according to the Conductor/Performer model, processing for a deadline miss exception (such a state that the processing corresponding to one period could not be completed within a specified time from driving of the Conductor process) is conducted by signal notification to the Conductor process. Since a signal handler has typically the same priority as a subject process does, there is a possibility that execution of a process of another stream will be delayed by the signal handler processing. In other words, there is a possibility that the processing delay of one stream will cause a processing delay of another stream.
A video conference system and a video-on-demand system are those applications which process consecutive media generated by digitizing speeches and dynamic images in real-time in a distributed environment using a network. Unless the communication data quantity per unit time is assured in the data communication in these applications, the data transfer cannot meet a playback processing of the consecutive media, so that the playback processing becomes incomplete and the interruption of the speech and disturbance of the images occur. In other words, to accomplish these applications, a data communication assuring the bandwidth, which in turn assures the communication data quantity per unit time, becomes essentially necessary.
The multimedia LAN system described above assures the bandwidth by using the time-slot for synchronization signal transfer and the time-slot for asynchronous signal transfer but when compared with the conventional LAN system using the CSMA/CD system, this system involves the problem that a specific apparatus which enables all the computers constituting the LAN system to establish synchronism throughout the whole LAN system must be provided. In other words, the existing LAN apparatus cannot be applied as they are and the change of the LAN specification is unavoidable.